package lc_LCP79_提取咒文;

import java.util.PriorityQueue;

public class Solution {

    int m, n;
    int[] d = new int[] { 0, 1, 0, -1, 1, 0, -1, 0 };

    public int extractMantra(String[] matrix, String mantra) {
        m = matrix.length;
        n = matrix[0].length();
        int k = mantra.length();
        boolean[][] visit = new boolean[k][m * n];// mantra index, index(x,y)
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]); // 操作次数，index，位置
        queue.add(new int[] { 0, 0, 0, 0 });
        visit[0][0] = true;
        while (!queue.isEmpty()) {
            int[] c = queue.poll();
            int t = c[0], index = c[1], x = c[2], y = c[3];
            if (index == k) {// i已经抵达mantra最后
                return t;
            }
            // 同层继续走
            for (int i = 0; i < 8; i += 2) {
                int nx = x + d[i], ny = y + d[i + 1];
                int pos = index(nx, ny);
                if (range(nx, ny) && !visit[index][pos]) {
                    visit[index][pos] = true;
                    queue.add(new int[] { t + 1, index, nx, ny });
                }
            }
            // 跳层
            if (matrix[x].charAt(y) == mantra.charAt(index)) {
                queue.add(new int[] { t + 1, index + 1, x, y });
            }
        }
        return -1;
    }

    private boolean range(int x, int y) {
        if (x >= 0 && x < m && y >= 0 && y < n) {
            return true;
        }
        return false;
    }

    private int index(int x, int y) {
        return x * n + y;
    }

    public static void main(String[] args) {
        System.out.println("LCP 79. 提取咒文");
    }
}
